package ch5.part5;

/**
 * 判断一个正整数是否为2的整数次幂
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class PowerOf2 {

    private static int TWO = 2;

    /**
     * 通过依次将(2^n)与目标数进行对比，相等则为true
     * 时间复杂度：O(n) = logn
     *
     * @param num 目标数
     * @return 是否为2的整数次幂
     */
    private static boolean calcV1(int num) {
        if (num != 1 && num % TWO != 0) {
            return false;
        }

        int i = 0, temp = 1;
        while (temp <= num) {
            if (temp == num) {
                return true;
            }
            temp = temp << 1;
        }
        return false;
    }

    /**
     * 将num和(num-1)做位与运算，结果为0即为true
     * 时间复杂度：O(n) = 1
     *
     * @param num 目标数
     * @return 是否为2的整数次幂
     */
    private static boolean calcV2(int num) {
        return (num & num - 1) == 0;
    }

    public static void main(String[] args) {
        System.out.println(calcV1(16));
        System.out.println(calcV2(16));
        System.out.println(calcV1(3678));
        System.out.println(calcV2(3678));
    }

}
